#include <iostream>
/*
  Given an array of size N in which every number is between 1 and N, determine if
  there are any duplicates in it. You are allowed to destroy the array if you
  like.
*/

using namespace std;

void swap(int &a, int &b){
	int c=a;
	a=b;
	b=c;
}

bool determine(int* a, int N){
  for (int i = 0; i < N; i++){
    int x = a[i];
    while (x-1 != i){
      if (x == a[x-1])
        return true;//duplicate found
      else
        swap(x,a[x-1]);
    }
    a[i] = x;
  }
  return false;
}
int main(){
  int arr[]={7,6,5,4,3,2,2};
  cout << determine(arr,sizeof(arr)/sizeof(int))<<endl;
  system("PAUSE");
}
